package com.sheng.leetcode.year2022.month11.day17;

import org.junit.Test;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author liusheng
 * @date 2022/11/17
 *<p>
 * 792. 匹配子序列的单词数<p>
 *<p>
 * 给定字符串 s 和字符串数组 words, 返回  words[i] 中是s的子序列的单词个数 。<p>
 * 字符串的 子序列 是从原始字符串中生成的新字符串，<p>
 * 可以从中删去一些字符(可以是none)，而不改变其余字符的相对顺序。<p>
 * 例如， “ace” 是 “abcde” 的子序列。<p>
 *<p>
 * 示例 1:<p>
 * 输入: s = "abcde", words = ["a","bb","acd","ace"]<p>
 * 输出: 3<p>
 * 解释: 有三个是 s 的子序列的单词: "a", "acd", "ace"。<p>
 *<p>
 * 示例 2:<p>
 * 输入: s = "dsahjpjauf", words = ["ahjpjau","ja","ahbwzgqnuk","tnmlanowax"]<p>
 * 输出: 2<p>
 *<p>
 * 提示:<p>
 * 1 <= s.length <= 5 * 10^4<p>
 * 1 <= words.length <= 5000<p>
 * 1 <= words[i].length <= 50<p>
 * words[i]和 s 都只由小写字母组成。<p>
 */
public class LeetCode0792 {

    @Test
    public void test01() {
//        String s = "abcde";
//        String[] words = {"a","bb","acd","ace"};
//        String s = "dsahjpjauf";
//        String[] words = {"ahjpjau","ja","ahbwzgqnuk","tnmlanowax"};
        String s = "iwdlcxpyagegrcnrcylxolxlnhhwnxyzltiscrjztiivnpnzlubzpueihinsqdfvypdteztiodbhaqhxskupwulvkzhczdyoouym";
        String[] words = {
                // true
                "hhwnxyzltiscrjztiivnpnzlubzpueihinsqdfvyp",
                "vnpnzlubzpueihinsqdfvypdteztiodbha",
                "rcnrcylxolxlnhhwnxyzltiscrjztiivnpnzlubzpueihi",
                "dfvypdteztiodbhaqhxskupwulvk",
                "zltiscrjztii",
                // false
                "wdmbatbcewwittubryrqwwrvfkrmniomofygybeqfzusrgeart",
                "myzfexqmzxnbmmnhmpbddqhrwrobqzjiwdzzpyzodejysuuquc",
                "wxvrcbihbasohfvuwuxleesqeujxvjfvgwnhltenbspdgzsdrs",
                "nztyysfhfbfcihyeaqdarqxfpjunevabzafvbmpbtenarvyizv",
                "nivufheyodfjuggrbndyojeahrzgptikjfqufhwyhzyyjteahx"
        };
        System.out.println(new Solution().numMatchingSubseq(s, words));
    }
}

// 超时 ORZ
//class Solution {
//    public int numMatchingSubseq(String s, String[] words) {
//        /**
//         * 数组中字符串的每个字符都已相同的先后顺序存在于字符串 s 中
//         */
//        int count = 0;
//        // 循环字符
//        for (String word : words) {
//            int index = -1;
//            // 判断每个字符是否存在于字符串 s 中
//            boolean flag = true;
//            // 将当前循环的字符串转化为字符数组
//            char[] chars = word.toCharArray();
//            for (int i = 0; i < chars.length; i++) {
//                if (index == s.length() - 1) {
//                    flag = false;
//                }
//                // 将 j 的初始值赋值为 index + 1 跳过之前已经搜索过的字符串s
//                for (int j = index + 1; j < s.length(); j++) {
//                    if (s.charAt(j) == chars[i]) {
//                        // 找到对应字符在字符串中的位置，将该位置赋值给 index 并结束本次循环
//                        index = j;
//                        break;
//                    } else if (j == s.length() - 1) {
//                        // 代表在后续字符串中没有找到对应的字符，非子序列
//                        flag = false;
//                    }
//                }
//                // 判断是否为子序列
//                if (!flag) {
//                    break;
//                }
//            }
//            // 存在，则是子序列，将 count 自增
//            if (flag) {
//                count++;
//            }
//        }
//        return count;
//    }
//}

//朴素判定某个字符串是为另一字符串的子序列的复杂度为 O(n+m)O(n + m)O(n+m)，对于本题共有 500050005000 个字符串需要判定，
// 每个字符串最多长为 505050，因此整体计算量为 (5×104+50)×5000≈2.5×108(5 \times 10^4 + 50) \times 5000 \approx 2.5 \times 10^8 ，会超时。
//不可避免的是，我们要对每个 words[i]words[i]words[i] 进行检查，因此优化的思路可放在如何优化单个 words[i]words[i]words[i] 的判定操作。
//朴素的判定过程需要使用双指针扫描两个字符串，其中对于原串的扫描，会有大量的字符会被跳过（无效匹配），即只有两指针对应的字符相同时，匹配串指针才会后移。
//我们考虑如何优化这部分无效匹配。
//对于任意一个 w=words[i]w = words[i]w=words[i] 而言，假设我们当前匹配到 w[j]w[j]w[j] 位置，
//此时我们已经明确下一个待匹配的字符为 w[j+1]w[j + 1]w[j+1]，因此我们可以直接在 s 中字符为 w[j+1]w[j + 1]w[j+1] 的位置中找候选。
//具体的，我们可以使用哈希表 map 对 s 进行预处理：以字符 c=s[i]c = s[i]c=s[i] 为哈希表的 key，对应的下标 iii 集合为 value，
//由于我们从前往后处理 s 进行预处理，因此对于所有的 value 均满足递增性质。
//举个 🌰 : 对于 s = abcabc 而言，预处理的哈希表为 {a=[0,3], b=[1,4], c=[2,5]}
//最后考虑如何判定某个 w=words[i]w = words[i]w=words[i] 是否满足要求：待匹配字符串 w 长度为 m，
//我们从前往后对 w 进行判定，假设当前判待匹配位置为 w[i]w[i]w[i]，我们使用变量 idx 代表能够满足匹配 w[0:i]w[0:i]w[0:i] 的最小下标（贪心思路）。
//对于匹配的 w[i]w[i]w[i] 字符，可以等价为在 map[w[i]] 中找到第一个大于 idx 的下标，
//含义在原串 s 中找到字符为 w[i] 且下标大于 idx 的最小值，由于我们所有的 map[X] 均满足单调递增，该过程可使用「二分」进行。
//
class Solution {
    public int numMatchingSubseq(String s, String[] words) {
        // n：字符串 s 的 长度，ans：子序列的数量
        int n = s.length(), ans = 0;
        // key 是字符，value 是字符在字符串 s 中出现位置的索引的集合
        Map<Character, List<Integer>> map = new HashMap<>();
        // 循环字符串 s
        for (int i = 0; i < n; i++) {
            // 以字符串 s 中的每个字符为 key 获取 map 集合中对应的 value，如果没有则新创建一个 list
            List<Integer> list = map.getOrDefault(s.charAt(i), new ArrayList<>());
            // 将当前索引加入集合 list 中
            list.add(i);
            // 以字符为 key ，存放了 对应字符位置的索引集合为 value，放入map集合中
            map.put(s.charAt(i), list);
        }
        // 循环字符串数组 words
        for (String w : words) {
            // ok 用来判断字符串 w 是否为字符串 s 的子序列
            boolean ok = true;
            // m：字符串 w 的长度，idx：s 中和字符串 w 对应字符所在的位置
            int m = w.length(), idx = -1;
            // 循环字符串 w 中的每一个字符
            for (int i = 0; i < m && ok; i++) {
                // 获取当前字符在字符串 s 中对应的索引的集合
                List<Integer> list = map.getOrDefault(w.charAt(i), new ArrayList<>());
                // 在集合 list 中进行二分查找，l：左端点，r：右端点
                int l = 0, r = list.size() - 1;
                // 如果 l 小余 r 则进行循环
                while (l < r) {
                    // mid：左右的中间点
                    int mid = l + r >> 1;
                    // 如果 中间点对应的索引大于 idx
                    if (list.get(mid) > idx) {
                        // 将中间点的值赋值给右端点 r
                        r = mid;
                    } else {
                        // 将中间点的值加 1 后赋值给左端点 l
                        l = mid + 1;
                    }
                }
                // 如果右端点小余 0 或者集合中右端点 r 对应的索引小余等于 idx
                if (r < 0 || list.get(r) <= idx) {
                    // 代表要么字符串 s 中不存在这个字符，要么字符串 s 中的该字符位于上一个字符的前面，不满足条件
                    ok = false;
                } else {
                    // 代表找到了当前字符在字符串 s 中最小索引，并将该索引赋值给 idx
                    idx = list.get(r);
                }
            }
            // ok 为 true 代表当前字符串是子序列，ans自增
            if (ok) {
                ans++;
            }
        }
        // 返回
        return ans;
    }
}
//
//作者：宫水三叶
//链接：https://leetcode.cn/problems/number-of-matching-subsequences/solutions/1975585/by-ac_oier-u1ox/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
